/****************************************************************************
*																			*
*							cryptlib Prime Sieve							*
*						Copyright Peter Gutmann 2012-2014					*
*																			*
****************************************************************************/

#define PKC_CONTEXT		/* Indicate that we're working with PKC contexts */
#include "crypt.h"
#if defined( INC_ALL )
  #include "context.h"
  #include "keygen.h"
#else
  #include "context/context.h"
  #include "context/keygen.h"
#endif /* Compiler-specific includes */

#ifdef USE_PKC

/****************************************************************************
*																			*
*								Table of Primes								*
*																			*
****************************************************************************/

/* First 2000 primes, generated using PARI/GP with:

	for( n = 1, 2000, print( prime( n ) ) )

   but that could just as easily have been done using one of a million Sieve 
   of Eratosthenes programs */

static const int primeTbl[ PRIME_TABLE_SIZE + 2 ] = {
		2,	   3,	  5,	 7,	   11,	  13,	 17,	19,	   23,	  29,
	   31,    37,    41,    43,    47,    53,    59,    61,    67,    71,
	   73,    79,    83,    89,    97,   101,   103,   107,   109,   113,
	  127,   131,   137,   139,   149,   151,   157,   163,   167,   173,
	  179,   181,   191,   193,   197,   199,   211,   223,   227,   229,
	  233,   239,   241,   251,   257,   263,   269,   271,   277,   281,
	  283,   293,   307,   311,   313,   317,   331,   337,   347,   349,
	  353,   359,   367,   373,   379,   383,   389,   397,   401,   409,
	  419,   421,   431,   433,   439,   443,   449,   457,   461,   463,
	  467,   479,   487,   491,   499,   503,   509,   521,   523,   541,
#if PRIME_TABLE_SIZE > 100
	  547,   557,   563,   569,   571,   577,   587,   593,   599,   601,
	  607,   613,   617,   619,   631,   641,   643,   647,   653,   659,
	  661,   673,   677,   683,   691,   701,   709,   719,   727,   733,
	  739,   743,   751,   757,   761,   769,   773,   787,   797,   809,
	  811,   821,   823,   827,   829,   839,   853,   857,   859,   863,
	  877,   881,   883,   887,   907,   911,   919,   929,   937,   941,
	  947,   953,   967,   971,   977,   983,   991,   997,  1009,  1013,
	 1019,  1021,  1031,  1033,  1039,  1049,  1051,  1061,  1063,  1069,
	 1087,  1091,  1093,  1097,  1103,  1109,  1117,  1123,  1129,  1151,
	 1153,  1163,  1171,  1181,  1187,  1193,  1201,  1213,  1217,  1223,
	 1229,  1231,  1237,  1249,  1259,  1277,  1279,  1283,  1289,  1291,
	 1297,  1301,  1303,  1307,  1319,  1321,  1327,  1361,  1367,  1373,
	 1381,  1399,  1409,  1423,  1427,  1429,  1433,  1439,  1447,  1451,
	 1453,  1459,  1471,  1481,  1483,  1487,  1489,  1493,  1499,  1511,
	 1523,  1531,  1543,  1549,  1553,  1559,  1567,  1571,  1579,  1583,
	 1597,  1601,  1607,  1609,  1613,  1619,  1621,  1627,  1637,  1657,
	 1663,  1667,  1669,  1693,  1697,  1699,  1709,  1721,  1723,  1733,
	 1741,  1747,  1753,  1759,  1777,  1783,  1787,  1789,  1801,  1811,
	 1823,  1831,  1847,  1861,  1867,  1871,  1873,  1877,  1879,  1889,
	 1901,  1907,  1913,  1931,  1933,  1949,  1951,  1973,  1979,  1987,
	 1993,  1997,  1999,  2003,  2011,  2017,  2027,  2029,  2039,  2053,
	 2063,  2069,  2081,  2083,  2087,  2089,  2099,  2111,  2113,  2129,
	 2131,  2137,  2141,  2143,  2153,  2161,  2179,  2203,  2207,  2213,
	 2221,  2237,  2239,  2243,  2251,  2267,  2269,  2273,  2281,  2287,
	 2293,  2297,  2309,  2311,  2333,  2339,  2341,  2347,  2351,  2357,
	 2371,  2377,  2381,  2383,  2389,  2393,  2399,  2411,  2417,  2423,
	 2437,  2441,  2447,  2459,  2467,  2473,  2477,  2503,  2521,  2531,
	 2539,  2543,  2549,  2551,  2557,  2579,  2591,  2593,  2609,  2617,
	 2621,  2633,  2647,  2657,  2659,  2663,  2671,  2677,  2683,  2687,
	 2689,  2693,  2699,  2707,  2711,  2713,  2719,  2729,  2731,  2741,
	 2749,  2753,  2767,  2777,  2789,  2791,  2797,  2801,  2803,  2819,
	 2833,  2837,  2843,  2851,  2857,  2861,  2879,  2887,  2897,  2903,
	 2909,  2917,  2927,  2939,  2953,  2957,  2963,  2969,  2971,  2999,
	 3001,  3011,  3019,  3023,  3037,  3041,  3049,  3061,  3067,  3079,
	 3083,  3089,  3109,  3119,  3121,  3137,  3163,  3167,  3169,  3181,
	 3187,  3191,  3203,  3209,  3217,  3221,  3229,  3251,  3253,  3257,
	 3259,  3271,  3299,  3301,  3307,  3313,  3319,  3323,  3329,  3331,
	 3343,  3347,  3359,  3361,  3371,  3373,  3389,  3391,  3407,  3413,
	 3433,  3449,  3457,  3461,  3463,  3467,  3469,  3491,  3499,  3511,
	 3517,  3527,  3529,  3533,  3539,  3541,  3547,  3557,  3559,  3571,
	 3581,  3583,  3593,  3607,  3613,  3617,  3623,  3631,  3637,  3643,
	 3659,  3671,  3673,  3677,  3691,  3697,  3701,  3709,  3719,  3727,
	 3733,  3739,  3761,  3767,  3769,  3779,  3793,  3797,  3803,  3821,
	 3823,  3833,  3847,  3851,  3853,  3863,  3877,  3881,  3889,  3907,
	 3911,  3917,  3919,  3923,  3929,  3931,  3943,  3947,  3967,  3989,
	 4001,  4003,  4007,  4013,  4019,  4021,  4027,  4049,  4051,  4057,
	 4073,  4079,  4091,  4093,  4099,  4111,  4127,  4129,  4133,  4139,
	 4153,  4157,  4159,  4177,  4201,  4211,  4217,  4219,  4229,  4231,
	 4241,  4243,  4253,  4259,  4261,  4271,  4273,  4283,  4289,  4297,
	 4327,  4337,  4339,  4349,  4357,  4363,  4373,  4391,  4397,  4409,
	 4421,  4423,  4441,  4447,  4451,  4457,  4463,  4481,  4483,  4493,
	 4507,  4513,  4517,  4519,  4523,  4547,  4549,  4561,  4567,  4583,
	 4591,  4597,  4603,  4621,  4637,  4639,  4643,  4649,  4651,  4657,
	 4663,  4673,  4679,  4691,  4703,  4721,  4723,  4729,  4733,  4751,
	 4759,  4783,  4787,  4789,  4793,  4799,  4801,  4813,  4817,  4831,
	 4861,  4871,  4877,  4889,  4903,  4909,  4919,  4931,  4933,  4937,
	 4943,  4951,  4957,  4967,  4969,  4973,  4987,  4993,  4999,  5003,
	 5009,  5011,  5021,  5023,  5039,  5051,  5059,  5077,  5081,  5087,
	 5099,  5101,  5107,  5113,  5119,  5147,  5153,  5167,  5171,  5179,
	 5189,  5197,  5209,  5227,  5231,  5233,  5237,  5261,  5273,  5279,
	 5281,  5297,  5303,  5309,  5323,  5333,  5347,  5351,  5381,  5387,
	 5393,  5399,  5407,  5413,  5417,  5419,  5431,  5437,  5441,  5443,
	 5449,  5471,  5477,  5479,  5483,  5501,  5503,  5507,  5519,  5521,
	 5527,  5531,  5557,  5563,  5569,  5573,  5581,  5591,  5623,  5639,
	 5641,  5647,  5651,  5653,  5657,  5659,  5669,  5683,  5689,  5693,
	 5701,  5711,  5717,  5737,  5741,  5743,  5749,  5779,  5783,  5791,
	 5801,  5807,  5813,  5821,  5827,  5839,  5843,  5849,  5851,  5857,
	 5861,  5867,  5869,  5879,  5881,  5897,  5903,  5923,  5927,  5939,
	 5953,  5981,  5987,  6007,  6011,  6029,  6037,  6043,  6047,  6053,
	 6067,  6073,  6079,  6089,  6091,  6101,  6113,  6121,  6131,  6133,
	 6143,  6151,  6163,  6173,  6197,  6199,  6203,  6211,  6217,  6221,
	 6229,  6247,  6257,  6263,  6269,  6271,  6277,  6287,  6299,  6301,
	 6311,  6317,  6323,  6329,  6337,  6343,  6353,  6359,  6361,  6367,
	 6373,  6379,  6389,  6397,  6421,  6427,  6449,  6451,  6469,  6473,
	 6481,  6491,  6521,  6529,  6547,  6551,  6553,  6563,  6569,  6571,
	 6577,  6581,  6599,  6607,  6619,  6637,  6653,  6659,  6661,  6673,
	 6679,  6689,  6691,  6701,  6703,  6709,  6719,  6733,  6737,  6761,
	 6763,  6779,  6781,  6791,  6793,  6803,  6823,  6827,  6829,  6833,
	 6841,  6857,  6863,  6869,  6871,  6883,  6899,  6907,  6911,  6917,
	 6947,  6949,  6959,  6961,  6967,  6971,  6977,  6983,  6991,  6997,
	 7001,  7013,  7019,  7027,  7039,  7043,  7057,  7069,  7079,  7103,
	 7109,  7121,  7127,  7129,  7151,  7159,  7177,  7187,  7193,  7207,
	 7211,  7213,  7219,  7229,  7237,  7243,  7247,  7253,  7283,  7297,
	 7307,  7309,  7321,  7331,  7333,  7349,  7351,  7369,  7393,  7411,
	 7417,  7433,  7451,  7457,  7459,  7477,  7481,  7487,  7489,  7499,
	 7507,  7517,  7523,  7529,  7537,  7541,  7547,  7549,  7559,  7561,
	 7573,  7577,  7583,  7589,  7591,  7603,  7607,  7621,  7639,  7643,
	 7649,  7669,  7673,  7681,  7687,  7691,  7699,  7703,  7717,  7723,
	 7727,  7741,  7753,  7757,  7759,  7789,  7793,  7817,  7823,  7829,
	 7841,  7853,  7867,  7873,  7877,  7879,  7883,  7901,  7907,  7919,
	 7927,  7933,  7937,  7949,  7951,  7963,  7993,  8009,  8011,  8017,
	 8039,  8053,  8059,  8069,  8081,  8087,  8089,  8093,  8101,  8111,
	 8117,  8123,  8147,  8161,  8167,  8171,  8179,  8191,  8209,  8219,
	 8221,  8231,  8233,  8237,  8243,  8263,  8269,  8273,  8287,  8291,
	 8293,  8297,  8311,  8317,  8329,  8353,  8363,  8369,  8377,  8387,
	 8389,  8419,  8423,  8429,  8431,  8443,  8447,  8461,  8467,  8501,
	 8513,  8521,  8527,  8537,  8539,  8543,  8563,  8573,  8581,  8597,
	 8599,  8609,  8623,  8627,  8629,  8641,  8647,  8663,  8669,  8677,
	 8681,  8689,  8693,  8699,  8707,  8713,  8719,  8731,  8737,  8741,
	 8747,  8753,  8761,  8779,  8783,  8803,  8807,  8819,  8821,  8831,
	 8837,  8839,  8849,  8861,  8863,  8867,  8887,  8893,  8923,  8929,
	 8933,  8941,  8951,  8963,  8969,  8971,  8999,  9001,  9007,  9011,
	 9013,  9029,  9041,  9043,  9049,  9059,  9067,  9091,  9103,  9109,
	 9127,  9133,  9137,  9151,  9157,  9161,  9173,  9181,  9187,  9199,
	 9203,  9209,  9221,  9227,  9239,  9241,  9257,  9277,  9281,  9283,
	 9293,  9311,  9319,  9323,  9337,  9341,  9343,  9349,  9371,  9377,
	 9391,  9397,  9403,  9413,  9419,  9421,  9431,  9433,  9437,  9439,
	 9461,  9463,  9467,  9473,  9479,  9491,  9497,  9511,  9521,  9533,
	 9539,  9547,  9551,  9587,  9601,  9613,  9619,  9623,  9629,  9631,
	 9643,  9649,  9661,  9677,  9679,  9689,  9697,  9719,  9721,  9733,
	 9739,  9743,  9749,  9767,  9769,  9781,  9787,  9791,  9803,  9811,
	 9817,  9829,  9833,  9839,  9851,  9857,  9859,  9871,  9883,  9887,
	 9901,  9907,  9923,  9929,  9931,  9941,  9949,  9967,  9973, 10007,
	10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099,
	10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177,
	10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271,
	10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343,
	10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459,
	10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567,
	10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657,
	10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739,
	10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
	10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949,
	10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059,
	11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149,
	11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
	11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329,
	11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443,
	11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527,
	11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657,
	11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777,
	11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833,
	11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
	11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011,
	12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109,
	12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211,
	12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289,
	12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
	12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487,
	12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553,
	12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641,
	12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739,
	12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829,
	12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
	12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007,
	13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109,
	13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187,
	13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309,
	13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411,
	13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499,
	13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619,
	13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697,
	13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781,
	13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,
	13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
	13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081,
	14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197,
	14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323,
	14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419,
	14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519,
	14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593,
	14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
	14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767,
	14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851,
	14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947,
	14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
	15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149,
	15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259,
	15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319,
	15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401,
	15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497,
	15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607,
	15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679,
	15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773,
	15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881,
	15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971,
	15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
	16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183,
	16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267,
	16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381,
	16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481,
	16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
	16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691,
	16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811,
	16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903,
	16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993,
	17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093,
	17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
	17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317,
	17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389,
#endif /* PRIME_TABLE_SIZE > 100 */
	0, 0
	};

/****************************************************************************
*																			*
*								Fast Prime Sieve							*
*																			*
****************************************************************************/

/* The number of primes in the sieve (and their values) that result in a
   given number of candidates remaining from 40,000.  Even the first 100
   primes weed out 91% of all the candidates, and after 500 you're only
   removing a handful for each 100 extra primes.

	 Number		   Prime	Candidates left
				  Values	from 40,000
	--------	---------	---------------
	  0- 99		   0- 541		3564
	100-199		 541-1223		3175
	200-299		1223-1987		2969
	300-399		1987-2741		2845
	400-499		2741-3571		2755
	500-599		3571-4409		2688
	600-699		4409-5279		2629
	700-799		5279-6133		2593
	800-899		6133-6997		2555
	900-999		6997-7919		2521

  This means that at some point we reach the level of diminishing returns
  because we spend excessive time doing unnecessary trial divisions that 
  don't provide a useful result before we go on to a full M-R test anyway.
  The best number of trial divisions is dependent on the size of the prime 
  being tested, "A Performant, Misuse-Resistant API for Primality Testing" 
  by Massimo and Paterson has run the necessary tests for the best tradeoff, 
  which is calculated by getNoTrialDivs() below.

  There is in fact an even faster prime tester due to Dan Piponi that uses
  C++ templates as a universal computer and performs the primality test at
  compile time, however this requires the use of a fairly advanced C++
  compiler and isn't amenable to generating different primes.

  Finally, when we're doing a sieve of a singleton candidate we don't run 
  through the whole range of sieve values since we run into the law of 
  diminishing returns after a certain point.  The following value sieves 
  with every prime under 1000 */

#if PRIME_TABLE_SIZE < ( 21 * 8 )
  #define QUICK_CHECK_PRIMES	PRIME_TABLE_SIZE
#else
  #define QUICK_CHECK_PRIMES	( 21 * 8 )
#endif /* Small prime table */

/* Set up the sieve array for the number.  Every position that contains
   a zero is non-divisible by all of the small primes */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 3 ) ) \
int initSieve( IN_ARRAY( sieveSize ) BOOLEAN *sieveArray, 
			   IN_LENGTH_FIXED( SIEVE_SIZE ) const int sieveSize,
			   const BIGNUM *candidate )
	{
	LOOP_INDEX i;

	assert( isWritePtrDynamic( sieveArray, sieveSize * sizeof( BOOLEAN ) ) );
	assert( isReadPtr( candidate, sizeof( BIGNUM ) ) );

	REQUIRES( sieveSize == SIEVE_SIZE );

	memset( sieveArray, 0, sizeof( BOOLEAN ) * sieveSize );

	/* Walk down the list of primes marking the appropriate position in the
	   array as divisible by the prime.  We start at index 1 because the
	   candidate will never be divisible by 2 (== primeTbl[ 0 ]) */
	LOOP_MAX( i = 1, i < PRIME_TABLE_SIZE, i++ )
		{
		unsigned int step;
		BN_ULONG sieveIndex DUMMY_INIT;
		int bnStatus = BN_STATUS, LOOP_ITERATOR_ALT;

		ENSURES( LOOP_INVARIANT_MAX( i, 1, PRIME_TABLE_SIZE - 1 ) );

		/* Determine the correct start index for this value */
		step = primeTbl[ i ];
		CK( BN_mod_word( &sieveIndex, candidate, step ) );
		if( bnStatusError( bnStatus ) )
			return( getBnStatus( bnStatus ) );
		if( sieveIndex & 1 )
			sieveIndex = ( step - sieveIndex ) / 2;
		else
			{
			if( sieveIndex > 0 )
				sieveIndex = ( ( step * 2 ) - sieveIndex ) / 2;
			}

		/* If the start index falls outside the sieve, don't go any 
		   further */
		if( sieveIndex >= sieveSize )
			continue;

		/* Mark each multiple of the divisor as being divisible.
		
		   Note that many compilers will complain about the comparison for 
		   sieveIndex >= 0 being redundant because a BN_ULONG is unsigned, 
		   we leave it in anyway to be safe */
		LOOP_MAX_CHECKINC_ALT( sieveIndex >= 0 && sieveIndex < sieveSize,
							   sieveIndex += step ) 
			{
			ENSURES( LOOP_INVARIANT_MAX_XXX_ALT( sieveIndex, 0, sieveSize - 1 ) );

			sieveArray[ sieveIndex ] = TRUE;
			}
		ENSURES( LOOP_BOUND_OK_ALT );
		}
	ENSURES( LOOP_BOUND_OK );
	
	return( CRYPT_OK );
	}

/* An LFSR to step through each entry in the sieve array, avoiding a linear 
   search.  This isn't a true pseudorandom selection since all that it's 
   really doing is going through the numbers in a linear order with a 
   different starting point, but it's good enough as a randomiser.  In any
   case even a straight linear search isn't so bad, there's a slightly
   higher chance of selecting a prime that's preceded by a larger gap of
   non-primes, but in practice this slight bias isn't observable */

#define LFSR_POLYNOMIAL		0x1053
#define LFSR_MASK			0x1000

CHECK_RETVAL_RANGE( 0, SIEVE_SIZE ) \
int nextSievePosition( IN_INT_SHORT int value )
	{
	static_assert( LFSR_MASK == SIEVE_SIZE, "LFSR size" );
	
	REQUIRES( value > 0 && value < SIEVE_SIZE );

	/* Get the next value: Multiply by x and reduce by the polynomial */
	value <<= 1;
	if( value & LFSR_MASK )
		value ^= LFSR_POLYNOMIAL;

	ENSURES( value > 0 && value < SIEVE_SIZE );

	return( value );
	}

/* Get the n-th prime table entry, used in primeProbable() for the
   Miller-Rabin test */

CHECK_RETVAL_RANGE( 0, PRIME_TABLE_SIZE ) \
int getSieveEntry( IN_RANGE( 0, PRIME_TABLE_SIZE - 1 ) int position )
	{
	REQUIRES_EXT( position >= 0 && position < PRIME_TABLE_SIZE, 2 ); 

	return( primeTbl[ position ] );
	}

/* A one-off quick check for when we're evaluating whether an allegedly prime
   value seems kosher.  This is used in locations where someone is giving us
   what should be a prime, or at least something that shouldn't have small 
   prime factors, so it should be as quick as possible */

CHECK_RETVAL_BOOL STDC_NONNULL_ARG( ( 1 ) ) \
BOOLEAN primeCheckQuick( const BIGNUM *candidate )
	{
	const int candidateLen = BN_num_bytes( candidate );
	LOOP_INDEX i;

	assert( isReadPtr( candidate, sizeof( BIGNUM ) ) );

	REQUIRES_B( sanityCheckBignum( candidate ) );
	REQUIRES_B( candidateLen > 0 && candidateLen <= CRYPT_MAX_PKCSIZE );

	/* If we're checking a small value then we can use a direct machine
	   instruction for the check, this is both faster and avoids false 
	   positives when the value being checked is small enough to be 
	   present in the prime table */
	if( candidateLen < sizeof( BN_ULONG ) )
		{
		const BN_ULONG candidateWord = BN_get_word( candidate );

		ENSURES_B( candidateWord != BN_NAN );
		LOOP_MAX( i = 1, i < QUICK_CHECK_PRIMES && \
						 primeTbl[ i ] < candidateWord, i++ )
			{
			ENSURES_B( LOOP_INVARIANT_MAX( i, 1, QUICK_CHECK_PRIMES - 1 ) );

			if( candidateWord % primeTbl[ i ] == 0 )
				return( FALSE );
			}
		ENSURES_B( LOOP_BOUND_OK );

		return( TRUE );
		}

	LOOP_MAX( i = 0, i < QUICK_CHECK_PRIMES, i++ )
		{
		BN_ULONG result DUMMY_INIT;
		int bnStatus = BN_STATUS;

		ENSURES_B( LOOP_INVARIANT_MAX( i, 0, QUICK_CHECK_PRIMES - 1 ) );

		CK( BN_mod_word( &result, candidate, primeTbl[ i ] ) );
		if( bnStatusError( bnStatus ) || result == 0 )
			return( FALSE );
		}
	ENSURES_B( LOOP_BOUND_OK );

	return( TRUE );
	}
#endif /* USE_PKC */
